package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/06 20:32
 **/
public class Day22_3_Num18_FourSum {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> fourSum(int[] nums, int target) {
            if(nums.length < 4) return res;
            Arrays.sort(nums);
            int len = nums.length;
            for(int i = 0;i < len-3;i++){
                if(i > 0 && nums[i] == nums[i-1]) continue;
                if((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
                if((long)nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target) continue;

                for(int j = i+1;j < len-2;j++){
                    if(j > i+1 && nums[j] == nums[j-1]) continue;
                    if((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
                    if((long)nums[i] + nums[j] + nums[len-1] + nums[len-2] < target) continue;
                    int k = j+1,l = len-1;
                    while(k < l){
                        int sum = nums[i] + nums[j] + nums[k] + nums[l];
                        if(sum == target){
                            List<Integer> ret = new ArrayList<>();
                            ret.add(nums[i]);ret.add(nums[j]);ret.add(nums[k]);ret.add(nums[l]);
                            res.add(ret);
                            while(k < l && nums[k] == nums[k+1]) k++;
                            k++;
                            while(k < l && nums[l] == nums[l-1]) l--;
                            l--;
                        }else if(sum < target) k++;
                        else l--;
                    }
                }
            }
            return res;
        }
    }
}